1. Field of the Invention
The present invention relates to data processing systems and is more particularly concerned with processes for memory space allocation and deallocation.
2. Background Information
Effective memory management is essential to the performance of complex software systems. Modern data processing systems typically have one or more central processing units (CPUs) which access an area of real storage provided for that data processing system. Memory space may be used for such things as control blocks, buffers, data areas and state vectors. Effective storage allocation is required to support software performance without greatly increasing the amount of real storage required. An effective dynamic storage allocation algorithm is required to insure that areas of memory are reused as they become available. Without effective reuse, additional permanently assigned storage would be required for each purpose to ensure a low probability of exhausting each storage type.
The rate of obtaining storage may be greater than a thousand times per second and overall system throughput may be adversely effected by the required storage allocation processing time. Unfortunately, storage efficiency and CPU efficiency are usually tradeoffs in the selection of a dynamic storage allocation algorithm. Storage inefficiency is a result of fragmentation, both internal, the result of giving out more storage than requested (e.g., by rounding up to some boundary), and external, the "checkerboard" effect caused by alternating blocks of available and in-use storage. Processing inefficiency results when it becomes necessary to extensively search for a storage block that will satisfy the request for free storage (or to search for the proper place to "insert" a released item), and can be measured by the mean number of blocks inspected per request or release.
There have been many discussions of different types of dynamic storage allocation systems. Donald Knuth in The Art of Computer Programming, Vol. 1: Fundamental Algorithms, 2nd Edition, Addison Wesley Publishing Company, Inc., copyright 1973, discusses a variety of dynamic storage allocation techniques. Knuth discusses linked list techniques where available free storage is linked by pointers from one available block to the next and various selection algorithms for determining which block to use in allocating to meet a storage request. Knuth also discusses the problem of returning a block to the free storage list and the need to collapse adjacent available areas together in order to compact memory and avoid fragmentation. The process of "garbage collection" where an attempt is made to identify any unused allocated storage blocks and to combine these into the free storage list is also covered.
Other techniques of memory management and garbage collection are known in the prior art. Venton et al., U.S. Pat. No. 4,121,286 discuss a system of memory space allocation and deallocation that employs a master capability table to track the use and allocation of storage. Venton et al. suggest a method of garbage collection relying on the use of garbage bits and visited bits to determine which storage blocks have been used by the system. The system must periodically inspect all storage blocks to determine whether some may be reclaimed as "garbage".
McEntee et al., U.S. Pat. No. 4,797,810 provide a system and method for incremental garbage collection in a virtual address space. McEntee et al. divide the memory into new and old portions and periodically copy objects from old to new portions of the memory and reclaim any unused space from the old space. This technique has the disadvantage of requiring substantially greater amounts of memory space than will be used by the processor.
Bozman et al. in "Analysis of Free-Storage Algorithms --Revisited" in the IBM Systems Journal, Vol. 23, No. 1, 1984, discuss a variety of free storage algorithms for use in the IBM VM/SP control program. Bozman et al. discuss a variety of methods which can be used to improve storage allocation efficiencies and to measure the relative performance of various methods. In particular, Bozman et al. discuss a dynamic storage algorithm employed with the IBM VM/370 product that uses fixed size queues containing free storage elements of particular size which can be rapidly allocated without searching. The fixed size queues allow the processor to immediately find a storage element of a given size without any requirement for searching a linked list. If the request cannot be satisfied from a queue, a search is made of the linked list of available storage blocks. Bozman et al. discuss the need for periodic garbage collection in which all of the free storage present in the fixed size queues is returned to the free list and the queues recreated. A major disadvantage of this present method is the requirement for periodic garbage collection by processing all entries in the queues.